package class_4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Random;

public class Coding_nthMagicalNumber {
	public static int nthMagicalNumber(int n, int a, int b) {
		long lcm = lcm(a, b);//求解a,b的最小公倍数。
		long ans = 0L;//记录临界的右区间值。
		//l,r定范围
		long l = 0L;
		long r = (long)n * Math.min(a, b);
		//[1,n*a] || [1,n*b]显然存在>=n个的解。 但是范围太广了，需要放缩区间
		long m = 0L;
		//利用二分搜索找到临界点
		while(l<=r) {
			//由于开的long，不会越界。 这么写只是个人习惯。
			m = (l - r)/2 + r;
			/**
			 * m/a + m/b - m/(lcm) 容斥原理求解个数
			 * [1,m]被a整除的个数 + [1,m]被b整除的个数。
			 * 显然存在被a & b整除的重复解, 因此需要ab注意的最大公约数来排除重复解。
			 * 需要注意， 不能直接用m/(a*b)解决。会漏解。
			 * 调用lcm函数求解最小公倍数即可。
			 */
			if(m/a + m/b - m/(lcm) >= n) {
				ans = m;
				r = m - 1;
			}
			else {
				// <m
				l = m + 1;
			}
		}
		//结果要求返回int， 可能会溢出， 题目要求对10^9+7取模。
		return (int)(ans %((int)Math.pow(10,  9) + 7));
    }
	/**
	 * 欧几里得算法
	 * 辗转相除法求解正整数的最大公约数。
	 * 时间复杂度:O(logn ^ 3)
	 * @param a
	 * @param b
	 * @return
	 */
	public static long gcb(long a, long b) {
		return b==0?a:gcb(b,a%b);
	}
	/**
	 * 求解最小公倍数。利用最大公约数求解最小公倍数
	 * 时间复杂度:O(logn ^ 3)
	 * @param a
	 * @param b
	 * @return
	 */
	public static long lcm(long a, long b) {
		return (long)a/gcb(a,b) * b;
	}
	public static int a,b;
	public static int bound = 10001;//随机数右边界
	public static int n;//第n个神奇数字。
	public static Random random = new Random();
	public static void main(String[] args) throws IOException{
		//生成两个随机数
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			a = random.nextInt(0,bound);
			b = random.nextInt(0,bound);
			out.printf("n:%d, a:%d, b:%d \n", n,a,b);
			out.println("返回第n个数字（可能溢出）:"+ nthMagicalNumber(n,a,b));
		}
		out.flush();
		out.close();
	}
}
